home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / ai / algo.txt < prev    next >
Text File  |  1988-07-07  |  33KB  |  844 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.                    Expressing Procedural Algorithms in Prolog
  8.  
  9.                               Michael A. Covington
  10.  
  11.                              Research Report 01-0012
  12.                       Advanced Computational Methods Center
  13.                               University of Georgia
  14.                               Athens, Georgia 30602
  15.  
  16.                               May 26, 1986  4:25 pm
  17.  
  18.           --------------------------------------------------------------
  19.           This work was supported by PACER Grant 85PCR18 from Control
  20.           Data Corporation and by Grant Number INS-85-02477 from the
  21.           National Science Foundation. The opinions expressed here are
  22.           solely those of the author. The assistance of Donald Nute and
  23.           Andre Vellino is gratefully acknowledged. Printed copies of
  24.           this and other research reports are available free on request.
  25.           --------------------------------------------------------------
  26.  
  27.         With the increasing popularity of Prolog as an application
  28.         programming language, it is often necessary to develop Prolog
  29.         equivalents for algorithms that were originally expressed in 
  30.         procedure-oriented languages. This paper presents a number of
  31.         strategies for doing so. I assume that the reader is already
  32.         familiar with the basic mechanisms of Prolog -- unification
  33.         (matching), backtracking, and the like.
  34.  
  35.         Unless otherwise noted, the examples given here work both in full
  36.         "Edinburgh" or "DEC-10" Prolog (Clocksin and Mellish 1984) and in
  37.         Turbo Prolog (1986), which is a subset of the full language. The
  38.         examples are written in Turbo Prolog syntax, but with declarations
  39.         omitted for brevity. Full Prolog is used -- and noted as such --
  40.         when its features are needed.
  41.  
  42.         The procedural interpretation of logic
  43.  
  44.         Prolog is often described as a non-procedural language. In
  45.         reality, it is a semi-procedural language -- a compromise between
  46.         procedural and non-procedural programming, giving some of the
  47.         advantages of each. In a truly non-procedural language, the
  48.         programmer would provide only a logically rigorous set of
  49.         conditions that the program must fulfill; the computer would then
  50.         automatically generate an algorithm from them. Such things as the
  51.         order in which the conditions were written would have no effect.
  52.  
  53.         In the interest of efficiency, Prolog contains some procedural
  54.         elements. The Prolog programmer specifies not only the rules of
  55.         inference to be used in solving a problem, but also the order in
  56.         which they are to be tried. Crucially, the programmer can even
  57.         specify that some potential paths to a solution should not be
  58.         tried at all. This makes it possible to perform efficiently many
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.                                                                       2
  67.  
  68.         computations that would be severely inefficient, or even
  69.         impossible, in pure Prolog.
  70.  
  71.         The key principle of Prolog is the procedural interpretation of
  72.         logic. Consider the following Prolog rule set:
  73.  
  74.         [1]         in_north_america(X) :- in_usa(X).
  75.                     in_usa(X) :- in_georgia(X).
  76.                     in_georgia(atlanta).
  77.  
  78.         This can be interpreted as a set of facts ([2] below) or as a set
  79.         of procedure definitions ([3] below).
  80.  
  81.         [2]         X is in North America if X is in the USA.
  82.                     X is in the USA if X is in Georgia.
  83.                     Atlanta is in Georgia.
  84.  
  85.         [3]         To prove that X is in North America,
  86.                          prove that X is in the USA.
  87.                     To prove that X is in the USA,
  88.                          prove that X is in Georgia.
  89.                     To prove that Atlanta is in Georgia,
  90.                          do nothing.
  91.  
  92.         The unfamiliar task of drawing inferences from data is thereby
  93.         reduced to the very familiar task of calling procedures.
  94.  
  95.         In what follows I will unashamedly refer to Prolog predicate
  96.         definitions as procedures.
  97.  
  98.         Conditional execution
  99.  
  100.         One of the most important differences between Prolog and other
  101.         programming languages is that, in general, Prolog procedures have
  102.         multiple definitions (clauses), each applying under different
  103.         conditions. In Prolog, conditional execution is expressed, not
  104.         with if or case statements, but with these alternative definitions
  105.         of procedures.
  106.  
  107.         Consider for example how we might translate into Prolog the
  108.         following Pascal procedure:
  109.  
  110.         [4]         procedure writename(X:integer);
  111.                     begin
  112.                       case X of
  113.                         1: write('One');
  114.                         2: write('Two');
  115.                         3: write('Three')
  116.                       end
  117.                     end;
  118.  
  119.         This is done by giving writename three definitions:
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.                                                                       3
  133.  
  134.  
  135.         [5]         writename(1) :- write("One").
  136.                     writename(2) :- write("Two").
  137.                     writename(3) :- write("Three").
  138.  
  139.         Each definition matches in exactly one of the three cases. A
  140.         common mistake is to write the clauses as follows:
  141.  
  142.         [6]         /* bad style */
  143.  
  144.                     writename(X) :- X=1, write("One").
  145.                     writename(X) :- X=2, write("Two").
  146.                     writename(X) :- X=3, write("Three").
  147.  
  148.         This gives correct results but is needlessly inefficient. It is a
  149.         waste of time to go into an inapplicable clause, perform a test
  150.         that fails, backtrack out, and try another clause, when the use of
  151.         the inapplicable clause could have been avoided in the first
  152.         place.
  153.  
  154.         A key to effective programming in Prolog is making each logical
  155.         unit of the program into a separate procedure. Each if or case
  156.         statement should, in general, become a procedure call. For
  157.         example, the hypothetical Pascal procedure:
  158.  
  159.         [7]         procedure a(X:integer);
  160.                     begin
  161.                       b;
  162.                       if X=0 then c else d;
  163.                       e
  164.                     end;
  165.  
  166.         should go into Prolog as follows:
  167.  
  168.         [8]         a(X) :- b,
  169.                             c_or_d(X),
  170.                             e.
  171.  
  172.                     c_or_d(0) :- c.
  173.                     c_or_d(X) :- X<>0, d.
  174.  
  175.         This imposes a disciplined organization on the program that is
  176.         even more rigorous than the structured ("go-to-less") programming
  177.         that serves as the basis of Pascal, Ada, and C.
  178.  
  179.         Guarded command sets
  180.  
  181.         As Kluzniak and Szpakowicz (1985) have pointed out, Dijkstra's
  182.         "guard" concept (Dijkstra 1975) is easily expressed in Prolog. A
  183.         guarded command set is a structure of the form
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.                                                                       4
  199.  
  200.         [9]         if
  201.                       C1 -> A1
  202.                       C2 -> A2
  203.                       C3 -> A3
  204.                     fi
  205.  
  206.         where C1, C2, and C3 are conditions and A1, A2, and A3 are the
  207.         corresponding actions. During program execution, all the
  208.         conditions are evaluated. If all of the conditions are false, the
  209.         program terminates. Otherwise, one of the actions corresponding to
  210.         a true condition is selected for execution.
  211.  
  212.         If exactly one condition is true, the guarded command set is
  213.         equivalent to an if-then or case statement. In fact, the Prolog
  214.         procedure "c_or_d" in [8] can be expressed in more Dijkstra-like
  215.         (though less efficient) form as:
  216.  
  217.         [10]        c_or_d(X) :- /* condition */ X=0,  /* action */ c.
  218.                     c_or_d(X) :- /* condition */ X<>0, /* action */ d.
  219.  
  220.         Guarded command sets were developed as part of a system for
  221.         deriving algorithms from formal specifications of the problems
  222.         they must solve. In Dijkstra's system, if more than one condition
  223.         is true, no assumptions are made about which action will be taken.
  224.         In Prolog, all possible actions will be taken on successive
  225.         backtracking passes, in the order in which they are given in the
  226.         program.
  227.  
  228.         The "cut" operator
  229.  
  230.         Let's consider another version of "writename" ([4] above) that
  231.         includes a "catch-all" clause to deal with numbers whose names are
  232.         not given. In many extended forms of Pascal, this can be expressed
  233.         as:
  234.  
  235.         [11]        procedure writename(X:integer);
  236.                     begin
  237.                       case X of
  238.                         1: write('One');
  239.                         2: write('Two');
  240.                         3: write('Three')
  241.                       else
  242.                         write('Out of range')
  243.                       end
  244.                     end;
  245.  
  246.         One way to express this in Prolog is the following:
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.                                                                       5
  265.  
  266.         [12]        writename(1) :- write("One").
  267.                     writename(2) :- write("Two").
  268.                     writename(3) :- write("Three").
  269.                     writename(X) :- X<1, write("Out of range").
  270.                     writename(X) :- X>3, write("Out of range").
  271.  
  272.         This gives correct results but lacks conciseness. In order to make
  273.         sure that only one clause is applicable to each number, we have
  274.         had to add two more clauses. What we would like to say is that the
  275.         program should print "Out of range" for any number that has not
  276.         matched any of the first three clauses. We could try to express
  277.         this as follows, with some lack of success:
  278.  
  279.         [13]        /* incorrect */
  280.                     writename(1) :- write("One").
  281.                     writename(2) :- write("Two").
  282.                     writename(3) :- write("Three").
  283.                     writename(_) :- write("Out of range").
  284.  
  285.         (Recall that the anonymous variable, written _, matches anything.)
  286.         The problem here is that the goal "writename(1)", for example,
  287.         matches both the first clause and the last clause. If a subsequent
  288.         goal fails and causes backtracking through this one, the goal
  289.         "writename(1)" will have two solutions, one that prints "One" and
  290.         one that prints "Out of range."
  291.  
  292.         We want "writename" to be deterministic, that is, to give exactly
  293.         one solution for any given set of parameters, and not give
  294.         alternative solutions upon backtracking. We would therefore like
  295.         to specify somehow that if any of the first three clauses
  296.         succeeds, the computer should not try the last clause. This can be
  297.         done with the "cut" operator (written as an exclamation mark). 
  298.  
  299.         The cut operator commits the computer to take a particular
  300.         solution (or potential solution) without trying alternatives.
  301.         Suppose for example that we have the following rule set:
  302.  
  303.         [14]        b :- c, d, !, e, f.
  304.                     b :- g, h.
  305.  
  306.         and that the current goal is "b". If we take the first clause and
  307.         execute the cut, then it becomes impossible to look for
  308.         alternative solutions to "c" and "d" (the goals that precede the
  309.         cut in the same clause) or to "b" (the goal that invoked the
  310.         clause containing the cut). It remains possible, of course, to
  311.         backtrack all the way past "b" and look for alternatives to the
  312.         clause that caused "b" to be invoked.
  313.  
  314.         What we need to do in [13] is to put a cut in each of the first
  315.         three clauses. This changes their meaning slightly, so that the
  316.         first clause (for example) says, "If the parameter is 1, then
  317.         write 'One' and do not try any other clauses."
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.                                                                       6
  331.  
  332.  
  333.         [15]        writename(1) :- !, write("One").
  334.                     writename(2) :- !, write("Two").
  335.                     writename(3) :- !, write("Three").
  336.                     writename(_) :- write("Out of range").
  337.  
  338.         Since "write" is deterministic, it does not matter whether the cut
  339.         is written before or after the call to "write". However, programs
  340.         are usually more readable if cuts are made as early as possible.
  341.  
  342.         Making procedure calls always succeed or always fail
  343.  
  344.         In order to control the flow of program execution, it is often
  345.         necessary to guarantee that a goal will always succeed regardless
  346.         of the results of the computation that it performs. Occasionally,
  347.         it is necessary to guarantee that a goal will always fail.
  348.  
  349.         An easy way to make any procedure succeed is to add an additional
  350.         clause to it that succeeds with any parameters, and is tried last,
  351.         thus:
  352.  
  353.         [16]        f(X,Y) :- X < Y, !, write("X less than Y").
  354.                     f(_,_).
  355.  
  356.         A call to "f" succeeds with any parameters; it may or may not
  357.         print its message, but it will certainly not return failure and
  358.         hence will not cause backtracking in the procedure that invoked
  359.         it. Moreover, because of the cut, "f" is deterministic. The cut
  360.         prevents the second clause from being used to generate a second
  361.         solution with parameters that have already succeeded with the
  362.         first clause.
  363.  
  364.         Similarly, a procedure can be guaranteed to fail by adding cut and
  365.         fail at the end of each of its definitions, thus:
  366.  
  367.         [17]        g(X,Y) :- X<Y, write("X less than Y"), !, fail.
  368.                     g(X,Y) :- Y<X, write("Y less than X"), !, fail.
  369.  
  370.         Any call to "g" ultimately returns failure for either of two
  371.         reasons: either it doesn't match any of the clauses, or it matches
  372.         one of the clauses and ends with cut and fail. The cut is written
  373.         next to last so that it won't be executed unless all the other
  374.         steps of the clause have succeeded; as a result, it is still
  375.         possible to backtrack from one clause of "g" to another.
  376.  
  377.         In full Prolog, but not in Turbo Prolog, we can define procedures
  378.         "make_succeed" and "make_fail" that take a goal as a parameter,
  379.         thus:
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.                                                                       7
  397.  
  398.         [18]        make_succeed(Goal) :- call(Goal), !.
  399.                     make_succeed(_).
  400.  
  401.                     make_fail(Goal) :- call(Goal), !, fail.
  402.  
  403.         In some implementations, "call(Goal)" is written simply as "Goal".
  404.  
  405.         Likewise, in full Prolog but not in Turbo Prolog we can define the
  406.         procedure "once" which allows a goal to succeed exactly once, thus
  407.         making any goal deterministic:
  408.  
  409.         [19]        once(Goal) :- call(Goal), !.
  410.  
  411.         This procedure backtracks as much as necessary to get one
  412.         successful solution to "Goal", then stops. Thus, no matter how
  413.         many possible solutions there are to "f(p)", the goal "once(f(p))"
  414.         will return only the first solution. If "f(p)" has no solutions,
  415.         "once(f(p))" fails.
  416.  
  417.         Repetition through backtracking
  418.  
  419.         Prolog offers two ways to perform computations repetitively:
  420.         backtracking and recursion. Of the two, recursion is by far the
  421.         more versatile. However, there are some interesting uses for
  422.         backtracking, among them the construction of "repeat-fail" loops.
  423.         In Prolog implementations that lack tail recursion elimination
  424.         (see below), "repeat-fail" looping is the only kind of iteration
  425.         that can be performed ad infinitum without causing a stack
  426.         overflow.
  427.  
  428.         The predicate "repeat" is built into some Prolog implementations.
  429.         In most others, it can be defined as follows:
  430.  
  431.         [20]             repeat.
  432.                          repeat :- repeat.
  433.  
  434.         (The built-in version of "repeat" should be used if available,
  435.         since there are a few implementations in which the definition in
  436.         [20] does not prevent stack overflow.)
  437.  
  438.         "Repeat" always succeeds and has an infinite number of solutions.
  439.         Thus any procedure call bracketed between "repeat" and "fail" will
  440.         be tried over and over again, even if it only generates one
  441.         solution. For instance, the following goal displays an infinite
  442.         number of asterisks:
  443.  
  444.         [21]             repeat, write("*"), fail.
  445.  
  446.         The following Turbo Prolog procedure turns the computer into a
  447.         typewriter, accepting characters from the keyboard and displaying
  448.         them ad infinitum, until the user hits "Break" to abort the
  449.         program:
  450.  
  451.  
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.                                                                       8
  463.  
  464.  
  465.         [22]             typewriter :- repeat,
  466.                                        readchar(C),
  467.                                        write(C),
  468.                                        fail.
  469.  
  470.         The loop can be made to terminate by allowing it to succeed
  471.         eventually, so that backtracking stops. The following version of
  472.         "typewriter" stops when the user types a carriage return (ASCII
  473.         code 13):
  474.  
  475.         [23]             typewriter :- repeat,
  476.                                        readchar(C),
  477.                                        write(C),
  478.                                        C = '\13'.
  479.  
  480.         If C is equal to code 13, execution terminates; otherwise,
  481.         execution backtracks to "repeat" and proceeds forward again
  482.         through "readchar(C)" and "write(C)". 
  483.  
  484.         The looping in [23] can be restarted by the failure of a
  485.         subsequent goal (as in the compound goal "typewriter,fail"). To
  486.         prevent the loop from restarting unexpectedly, we need to add a
  487.         cut as follows:
  488.  
  489.         [24]             typewriter :- repeat,
  490.                                        readchar(C),
  491.                                        write(C),
  492.                                        C = '\13',
  493.                                        !.
  494.  
  495.         In effect, this forbids looking for alternative solutions to
  496.         "typewriter."
  497.  
  498.         There is a crucial difference between "repeat-fail" loops in
  499.         Prolog and repeat-until loops in Pascal. In Pascal, iteration is
  500.         always accomplished by executing all the statements in the loop,
  501.         then jumping from the end back to the beginning. In Prolog,
  502.         backtracking may cause control to jump backward from any goal to
  503.         any earlier goal that has alternative solutions. (The limiting
  504.         case is "repeat", which always has alternative solutions.)
  505.         Moreover, if any goal in a Prolog loop fails, subsequent goals
  506.         will not be attempted.
  507.  
  508.         A serious limitation of "repeat-fail" loops is that there is no
  509.         convenient way to pass information from one iteration to the next.
  510.         Prolog variables lose their values upon backtracking. Thus, there
  511.         is no easy way to make a "repeat-fail" loop accumulate a count or
  512.         total. (Information can be preserved by storing it in the
  513.         knowledge base, using "assert" and "retract", but this is usually
  514.         a slow process.) With recursion, information can be transmitted
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.                                                                       9
  529.  
  530.         from one pass to the next through the parameter list. This is the
  531.         main reason for preferring recursion as a looping mechanism.
  532.  
  533.         Recursion
  534.  
  535.         Most programmers are familiar with recursion as a means of
  536.         implementing some very specialized, task-within-a-task algorithms
  537.         such as tree searching and Quicksort. Indeed, Prolog lends itself
  538.         well to expressing recursive algorithms developed in Lisp. What is
  539.         not generally appreciated is that any iterative algorithm can be
  540.         expressed recursively.
  541.  
  542.         Here is the classic recursive algorithm for computing factorials,
  543.         expressed in Pascal and in Turbo Prolog. (Change "=" to "is" to
  544.         get standard Prolog.)
  545.  
  546.         [25]        function factorial(N:integer):integer;
  547.                     begin
  548.                       if N=0 then
  549.                         factorial:=1
  550.                       else
  551.                         factorial:=N*factorial(N-1);
  552.                     end;
  553.  
  554.         [26]        factorial(0,1).
  555.  
  556.                     factorial(N,FactN) :- N > 0,
  557.                                           M = N-1,
  558.                                           factorial(M,FactM),
  559.                                           FactN = N*FactM.
  560.  
  561.         This is straightforward; the procedure "factorial" calls itself to
  562.         compute the factorial of the next smaller integer, then uses the
  563.         result to compute the factorial of the integer in question. 
  564.  
  565.         Now consider an iterative algorithm to do the same thing:
  566.  
  567.         [27]        function factorial(N:integer):integer;
  568.                     var I,J:integer;
  569.                     begin
  570.                       I:=0;           /* Initialize */
  571.                       J:=1;
  572.                       while I<N do
  573.                         begin         /* Loop */
  574.                           I:=I+1;
  575.                           J:=J*I
  576.                         end;
  577.                       factorial:=J        /* Return result */
  578.                     end;
  579.  
  580.         In Pascal, this procedure does not call itself. Its Prolog
  581.  
  582.  
  583.  
  584.  
  585.  
  586.  
  587.  
  588.  
  589.  
  590.  
  591.  
  592.  
  593.  
  594.                                                                      10
  595.  
  596.         counterpart is a procedure that calls itself as its very last step
  597.         -- a procedure that is said to be tail recursive:
  598.  
  599.         [28]        factorial(N,FactN) :- fact_iter(N,FactN,0,1).
  600.  
  601.                     fact_iter(N,FactN,N,FactN).
  602.  
  603.                     fact_iter(N,FactN,I,J) :-
  604.                                      I < N,
  605.                                      NewI = I+1,
  606.                                      NewJ = J*NewI,
  607.                                      fact_iter(N,FactN,NewI,NewJ).
  608.  
  609.         Here the third and fourth parameters of "fact_iter" are state
  610.         variables that pass values from one iteration to the next. State
  611.         variables in Prolog correspond to variables that change their
  612.         values repeatedly in Pascal.
  613.  
  614.         Let's start by examining the recursive clause of "fact_iter". This
  615.         clause checks that I is still less than N, computes new values for
  616.         I and J, and finally calls itself with the new parameters. 
  617.  
  618.         The recursive call is the very last step in this clause, and in
  619.         addition, this whole clause is placed last so that, when it calls
  620.         itself, there will be no untried alternatives to be saved on the
  621.         stack. This ensures that the stack will not grow during the
  622.         iteration. (We will return to this point below.)
  623.  
  624.         Because Prolog variables cannot change their values, the
  625.         additional variables NewI and NewJ have to be introduced. In
  626.         Prolog (as in arithmetic, but not in most programming languages),
  627.         the statement
  628.  
  629.                          X = X+1
  630.  
  631.         is always false. So NewI and NewJ contain the values that will
  632.         replace I and J in the next iteration.
  633.  
  634.         The first clause of "fact_iter" serves to end the iteration when
  635.         the state variables reach their final values. A more Pascal-like
  636.         but less efficient way of writing this clause would be:
  637.  
  638.         [29]             fact(N,FactN,I,J) :- I = N, FactN = J.
  639.  
  640.         That is, if I is equal to N, then FactN (so far uninstantiated)
  641.         should be given the value of J. By writing this same clause more
  642.         concisely in [28], we make Prolog's unification mechanism do work
  643.         that would require explicit computational steps in other
  644.         languages.
  645.  
  646.         Most iterative algorithms can be expressed in Prolog by following
  647.         this pattern shown here. First transform other types of loops
  648.  
  649.  
  650.  
  651.  
  652.  
  653.  
  654.  
  655.  
  656.  
  657.  
  658.  
  659.  
  660.                                                                      11
  661.  
  662.         (e.g., for and repeat-until) into Pascal while loops. Then break
  663.         the computation into three stages: the initialization, the loop
  664.         itself, and any subsequent computation needed to return a result.
  665.  
  666.         Express the loop as a tail recursive clause (like the second
  667.         clause of "fact_iter") with the while-condition at the beginning.
  668.         Computations to be performed after the loop terminates are placed
  669.         into another, non-recursive, clause of the same procedure, which
  670.         is set up so that it executes only after the loop is finished.
  671.  
  672.         Finally, hide the whole thing behind a "front-end" procedure
  673.         ("factorial" in this example) which is what the rest of the
  674.         program actually calls. The front-end procedure passes its
  675.         parameters into the tail recursive procedure along with initial
  676.         values of the state variables. The art of expressing iteration
  677.         through tail recursion is dealt with extensively, in Lisp, in the
  678.         first chapter of Abelson and Sussman (1985).
  679.  
  680.         Why tail recursion is special
  681.  
  682.         Whenever one Prolog procedure calls another, two things are saved
  683.         on a pushdown stack: (1) a record of what remains to be done after
  684.         return (the continuation of the calling procedure), and (2) a
  685.         record of what alternative solutions remain to be tried (the
  686.         alternative set). Normally, the continuation and the alternative
  687.         set are represented by pointers into already existing data
  688.         structures, so that it does not take any more space to represent a
  689.         large set than a small one.
  690.  
  691.         Since every procedure call places information onto the stack, it
  692.         would seem that recursion would lead inevitably to stack overflow.
  693.         However, most Prolog implementations (including Turbo Prolog)
  694.         recognize a special case: if the continuation and the alternative
  695.         list are both empty, nothing need be placed on the stack. In this
  696.         case, instead of calling itself, such a procedure can simply place
  697.         new values into its parameters and jump back to the beginning of
  698.         itself. In effect, this transforms recursion into iteration. 
  699.  
  700.         A procedure that calls itself with an empty continuation and empty
  701.         alternative list is described as tail recursive; the process of
  702.         executing such a call without adding items to the stack is called
  703.         tail recursion elimination. (The elimination of tail recursion
  704.         does not mean that it should be banished from the program; on the
  705.         contrary, it should be used liberally because the implementation
  706.         transforms it into an efficient iterative process.)
  707.  
  708.         A quick way to verify that a particular Prolog implementation
  709.         performs tail recursion elimination is to try the following
  710.         predicate:
  711.  
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724.  
  725.  
  726.                                                                      12
  727.  
  728.         [30]             test(N) :- write(N),
  729.                                     nl,
  730.                                     M = N+1, 
  731.                                     test(M).
  732.  
  733.         (Again, this is Turbo Prolog syntax; change "=" to "is" to get
  734.         standard Prolog.) Start with the goal "test(1)" and see how long
  735.         execution continues. If the program runs for more than 10,000
  736.         iterations, it is a safe bet that tail recursion elimination is
  737.         taking place.
  738.  
  739.         Controlling the growth of the stack
  740.  
  741.         It is easy to recognize a recursive call that has an empty
  742.         continuation: the recursive call is the very last subgoal in the
  743.         clause that contains it. Determining whether the alternative set
  744.         is also empty takes somewhat more thought.
  745.  
  746.         One way to get an empty alternative set is to put the recursive
  747.         call in the last clause of a predicate, as in the iterative
  748.         factorial program ([28], repeated here for convenience):
  749.  
  750.         [31]        factorial(N,FactN) :- fact_iter(N,FactN,0,1).
  751.  
  752.                     fact_iter(N,FactN,N,FactN).
  753.  
  754.                     fact_iter(N,FactN,I,J) :-
  755.                                      I < N,
  756.                                      NewI = I+1,
  757.                                      NewJ = J*NewI,
  758.                                      fact_iter(N,FactN,NewI,NewJ).
  759.  
  760.         The recursive call only takes place when all other alternatives
  761.         have been exhausted. 
  762.  
  763.         The alternative set can also be made empty by using cut to rule
  764.         out alternatives, as in the following replacement for "fact_iter":
  765.  
  766.         [32]        fact_iter(N,FactN,I,J) :-
  767.                                      I < N,
  768.                                      NewI = I+1,
  769.                                      NewJ = J*NewI,
  770.                                      !,
  771.                                      fact_iter(N,FactN,NewI,NewJ).
  772.  
  773.                     fact_iter(N,FactN,N,FactN).
  774.  
  775.         Here the recursive call occurs in the first clause, but the cut
  776.         guarantees that the second clause need not be considered as an
  777.         alternative.
  778.  
  779.  
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788.  
  789.  
  790.  
  791.  
  792.                                                                      13
  793.  
  794.         Because "NewI = I+1" and "NewJ = J*NewI" are deterministic, the
  795.         cut can equally well be placed before them, as follows:
  796.  
  797.         [33]        fact_iter(N,FactN,I,J) :-
  798.                                      I < N,
  799.                                      !,
  800.                                      NewI = I+1,
  801.                                      NewJ = J*NewI,
  802.                                      fact_iter(N,FactN,NewI,NewJ).
  803.  
  804.                     fact_iter(N,FactN,N,FactN).
  805.  
  806.         Note that [32] and [33] ought to be more efficient than [31]. The
  807.         first clause of [31] succeeds only on the last iteration; the rest
  808.         of the time, the first clause fails and control proceeds to the
  809.         second clause. Thus, almost every iteration must try both clauses.
  810.         In [32] and [33], the order of the clauses is reversed, so that
  811.         the first clause is the one that will almost always succeed.
  812.         Moreover, this clause contains a cut so that whenever it succeeds,
  813.         no other clause will be tried. The result is that, in [32] and
  814.         [33], only one clause -- the last one -- is tried on every
  815.         iteration except the last.
  816.          
  817.         In actual tests using Turbo Prolog on an IBM PC, the times taken
  818.         to compute the factorial of 200 were 0.58 second for [31] and 0.54
  819.         second for [32] and [33]. The gain in efficiency was small because
  820.         the time saved by omitting the unnecessary test was only slightly
  821.         greater than the time needed to execute the extra cut. The gain
  822.         would have been much larger if the unnecessary clause had
  823.         contained time-consuming computations.
  824.  
  825.         References
  826.  
  827.         Abelson, Harold, and Sussman, Gerald Jay (1985) Structure and
  828.           Interpretation of Computer Programs. Cambridge, Massachusetts:
  829.           MIT Press.
  830.  
  831.         Clocksin, W. F., and Mellish, C. S. (1984) Programming in Prolog.
  832.           Second edition. Berlin: Springer-Verlag.
  833.  
  834.         Dijkstra, E. W. (1975) Guarded commands, nondeterminacy and formal
  835.           derivation of programs. Communications of the ACM 18.8:453-457.
  836.  
  837.         Kluzniak, Feliks, and Szpakowicz, Stanislaw (1985) Prolog for
  838.           Programmers. London: Academic Press.
  839.  
  840.         Turbo Prolog (1986) Version 1.0. Scotts Valley, California:
  841.           Borland International.
  842.  
  843. shed from the program; on the
  844.         contrary, it sho